package com.LeeCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 电话号码的字母组合
 */

public class Code017 {
    public static void main(String[] args) {
        String s = "2362";
        System.out.println(new Code017().letterCombinations(s));
    }

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.length() == 0)
            return res;

        HashMap<Character, List<Character>> map = new HashMap<>();
        int count = 0;
        for (int i = 2; i <= 9; i++) {
            List<Character> tmp = new ArrayList<>();
            tmp.add((char) ('a' + count));
            tmp.add((char) ('a' + count + 1));
            tmp.add((char) ('a' + count + 2));
            if (i == 7) {
                tmp.add((char) ('a' + count + 3));
                count++;
            }
            count += 3;
            map.put(Character.forDigit(i, 10), tmp);
        }
        map.get('9').add('z');
        backtrace(digits, res, new StringBuilder(), 0, map);
        return res;
    }

    public void backtrace(String digits, List<String> res, StringBuilder sb, int index, HashMap<Character, List<Character>> map) {
        if (index == digits.length()) {
            res.add(sb.toString());
        }

        if (index < digits.length()) {
            int len = map.get(digits.charAt(index)).size();
            for (int i = 0; i < len; i++) {
                sb.append(map.get(digits.charAt(index)).get(i));
                backtrace(digits, res, sb, index + 1, map);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}
